本篇同步發布於Blog: [解題] LeetCode - 392 Is Subsequence

平台：

LeetCode

題號：

392 - Is Subsequence

題目連結：

https://leetcode.com/problems/is-subsequence/

題目說明：

        輸入兩個字串s 與 t，確認是否s是t的子序列。也就是s所有的元素，都出現在t，且出現的前後順序保持不變。

比如範例輸入的 s = "abc", t = "ahbgdc"，abc都在t出現，且a與b與c的出現順序與在s一樣。

解題方法：

   　建立兩個索引值i 與 j，分別在s和t的開頭掃描，遇到相同字元的則一起遞增看下一個字元，否則只有j遞增再看t的下個字元。最後如果i索引值掃描完s，代表s是t的子序列。

比如s = "abc", t = "ahbgdc"，初始化i = 0, j = 0

1. s[i] = 'a' = t[j] = 'a', 所以i = 1, j = 1
2. s[i] = 'b' != t[j] = 'h', 所以i = 1, j = 2
3. s[i] = 'b' = t[j] = 'b', 所以i = 2, j = 3
4. s[i] = 'c' != t[j] = 'g', 所以i = 2, j = 4
5. s[i] = 'c' != t[j] = 'd', 所以i = 2, j = 5
6. s[i] = 'c' = t[j] = 'c', 所以i = 3, j = 6

最後i已經都掃描過s字串，所以會是t的子序列。

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
#include <string>
using namespace std;
 
 
class Solution {
public:
    bool isSubsequence(string s, string t) {
        bool isSub = false;
        int i,j;
        for(i = 0, j = 0; i < s.length() && j < t.length();){
            if(s[i] == t[j]){
                i++;
                j++;
            }
            else{
                j++;
            }
        }
 
        if(i >= s.length()){
            isSub = true;
        }
 
        return isSub;
    }
};
 
int main() {
	Solution sol;
	cout << sol.isSubsequence("abc", "ahbgdc") << endl;
	return 0;
}

using System;

namespace LeetCode392
{
    public class Solution
    {
        public bool IsSubsequence(string s, string t)
        {
            bool isSub = false;
            int i, j;
            for (i = 0, j = 0; i < s.Length && j < t.Length;)
            {
                if (s[i] == t[j])
                {
                    i++;
                    j++;
                }
                else
                {
                    j++;
                }
            }

            if (i >= s.Length)
            {
                isSub = true;
            }

            return isSub;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(new Solution().IsSubsequence("abc", "ahbgdc"));
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/300-399/392.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/300-399/392.cs